package com.eddie.huffmancode;

import java.io.*;
import java.util.*;

/**
 * @author Eddie
 * @date 2022/08/12 09:16
 **/
public class HuffmanCode {
    public static void main(String[] args) {
//        zipFile("D://视频/Counter-strike  Global Offensive/Counter-strike  Global Offensive 2022.02.16 - 16.47.50.01.mp4", "D://视频/Counter-strike  Global Offensive/dspTest.zip");
//        System.out.println("压缩完成");
        //解压文件
        unZipFile("D://视频/Counter-strike  Global Offensive/dspTest.zip", "D://视频/Counter-strike  Global Offensive/unZipTest.mp4");
//        String content = "i like like like java do you like a java";
//        byte[] contentBytes = content.getBytes();
        //当前40字符
//        List<Node> nodes = getNodes(contentBytes);
//        Node root = createHuffmanTree(nodes);
//        preOrder(root);
//
//        //测试是否生成了对应的哈夫曼编码
//        getCodes(root, "", stringBuilder);
//        System.out.println("生成的哈夫曼表为:" + huffmanCodes);
//
//        //测试重载方法是否成功
//        Map<Byte, String> huffmanCodes = getCodes(root);
//        System.out.println("生成的哈夫曼表为:" + huffmanCodes);
//
//        //长度17
//        byte[] zip = zip(contentBytes, huffmanCodes);
//        System.out.println("哈夫曼编码过后的bytes=" + Arrays.toString(zip));
        //发送赫夫曼编码过后的数组
        //调用整合好的方法
//        byte[] huffmanCodesBytes = huffmanZip(contentBytes);
//        System.out.println("压缩后的结果是：" + Arrays.toString(huffmanCodesBytes)
//                + "\n长度为：" + huffmanCodesBytes.length
//                + "\n压缩率为：" + (((double) contentBytes.length - (double) huffmanCodesBytes.length) / contentBytes.length) * 100 + "%");
//        //如何将这个数据进行解压(解码)
//
//        //测试byteToBitString方法
//        System.out.println(byteToBitString(true, (byte) -88));
        //解码
//        byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
//        System.out.println(new String(sourceBytes));

    }

    /**
     * 完成压缩文件的解压
     *
     * @param zipFile  准备解压的文件
     * @param destFile 解压的目标文件夹
     */
    public static void unZipFile(String zipFile, String destFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //定义文件输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组和 huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);
            //将bytes数组写入目标文件
            os = new FileOutputStream(destFile);
            //写数据到文件中
            os.write(bytes);
        } catch (IOException | ClassNotFoundException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                Objects.requireNonNull(is).close();
                Objects.requireNonNull(ois).close();
                Objects.requireNonNull(os).close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }

    /**
     * 将一个文件进行压缩
     *
     * @param srcFile 要压缩的文件的全路径
     * @param dstFile 压缩后的存放目录
     */
    public static void zipFile(String srcFile, String dstFile) {
        //创建输出流

        //创建一个文件的输入流
        FileInputStream is = null;
        FileOutputStream os = null;
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一的byte[],available获取源文件字节大小
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);
            //直接对源文件压缩
            byte[] huffmanZip = huffmanZip(b);
            //创建一个文件的输出流
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutPutStream
            oos = new ObjectOutputStream(os);
            //这里先把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanZip);
            //这里以对象流的方式写入赫夫曼编码，是为了以后恢复源文件时使用
            //注意：一定要把赫夫曼编码写入压缩文件，否则以后恢复不了
            //因为在调用huffmanZip方法时，调用了getCodes方法：内部设置了huffmanCodes -》 赫夫曼编码，所以这里直接存入
            oos.writeObject(huffmanCodes);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                Objects.requireNonNull(is).close();
                Objects.requireNonNull(os).close();
                Objects.requireNonNull(oos).close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    /*
     * 完成数据的解压：
     * 思路：
     * 1、将huffmanCodeBytes:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
     *    重新转成 赫夫曼编码对应的二进制字符串 "1010100010111..."
     * 2、赫夫曼编码对应的二进制字符串"1010100010111..." => 对照赫夫曼编码转为
     *    => "i like like like java do you like a java"
     */

    /**
     * 完成对压缩数据的解码
     *
     * @param huffmanCodes 哈夫曼编码表map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //1、先得到huffmanBytes对应的二进制字符串。形式=>10101000...
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成二进制的字符串
        //为每一个字符获取它的二进制字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            String s = byteToBitString(!flag, huffmanBytes[i]);
            stringBuilder.append(s);
        }
        //把字符串按照指定的赫夫曼编码进行解码
        //把赫夫曼编码表进行调换，因为要反向查询a->100 100->a
        Map<String, Byte> map = new HashMap<>();
        //开始调换存储
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        //创建一个集合存放byte
        List<Byte> list = new ArrayList<>();
        //i可以理解为是一个索引,扫描string Builder
        for (int i = 0; i < stringBuilder.length(); ) {
            //小的计数器
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //取出一'1':'0'
                //i不动，让count移动，直到匹配到一个字符
                /*
                   说明：
                   1、在for循环时，到下标为i的二进制数时，给定一个count变量，他的初始值为1
                   2、在里面创建一个while循环，每一次都会取出当前string Builder的第i,i+count值作为key去map里查找
                      如果查到就直接设置为对应字符，否则count++，下一次while循环时就会在stringBuilder-i起始的位置上
                      向右扩展count的值递增一位，直至查找到
                 */
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                //说明没有匹配到
                if (b == null) {
                    count++;
                } else {
                    //匹配到了跳出循环
                    flag = false;
                }
            }
            //向集合中添加找到的字符（b）
            list.add(b);
            //这里是让i直接移动到找到字符的位置上
            //这样操作是为了让下一次循环直接开始向下一个字符查找，否则会找到错误的
            i += count;
        }
        //当for循环结束后，List中存放了所有的字符
        //把list中存放的所有数据存放到 byte[]
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

    /**
     * 将一个byte转成一个二进制字符串
     *
     * @param flag 标识是否需要补高位,如果为真表示需要补高位，为假表示不补，如果是最后一个字节，无需补高位
     *             因为最后一位如果补位得到的结果会是错误的
     * @param b    传入的byte值
     * @return 是b对应的二进制字符串（注意：是按补码返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        //使用一个遍历保存b
        int temp = b;
        //如果是正数，还存在一个补高位的问题
        //如果需要就或运算
        if (flag) {
            //按位或 256 = 1 0000 0000 | 1= 0000 0001 => 1 0000 0001
            //亮计算规则：相同位置的两个二进制数 有1结果就是1 否则为0
            temp |= 256;
        }
        //Integer.toBinaryString(temp)返回的是temp对应的二进制补码
        String str = Integer.toBinaryString(temp);
        //如果需要的话就截取8未返回，否则直接返回
        if (flag) {
            //截取返回的二进制补码 -> 取后八位
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    /**
     * 使用一个方法，将前面的方法封装起来，便于调用
     *
     * @param bytes 原始的字符串对应的字节数组
     *              return 经过赫夫曼编码处理后的字节数组（压缩后的数组）
     */
    private static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        //根据nodes创建赫夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        //根据赫夫曼树创建对应的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        //根据赫夫曼编码对原始数据压缩,得到压缩后的赫夫曼编码字节数组
        return zip(bytes, huffmanCodes);
    }

    /**
     * 编写一个方法，将字符串对应的byte数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码表压缩后的byte[]
     *
     * @param bytes        原始字符串对应的byte[]
     * @param huffmanCodes 生成的赫夫曼编码map
     * @return 返回赫夫曼编码处理后的byte[]
     * 举例： String content = "i like like like java do you like a java" =》
     * byte[] contentBytes = content.getBytes();
     * 返回的是： "1010100010...等”
     * 这个字符串对应的byte[] => 八位对应一个byte,huffmanCodes
     * huffmanCodes[0] => 10101000(补码) => byte [推导 10101000 => 10101000-1 => 10100111(反码)=>11011000 => -88]
     * huffmanCodes[0] = -88
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1、利用huffmanCodes将bytes转成赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历bytes
        for (byte b : bytes) {
            //从哈夫曼编码中获取该byte值对应的哈夫曼编码
            stringBuilder.append(huffmanCodes.get(b));
        }
        //将string Builder转为byte[]
        //下面代码可以用一句话搞定int len = (stringBuilder.length()+7) / 8;
        int len;
        //统计返回的byte[] huffmanCodes长度
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建一个存储压缩后的byte数组
        byte[] huffmanCodesBytes = new byte[len];
        //记录是第几个byte
        int index = 0;
        //因为是每8位对应一个byte，所以步长+8
        for (int i = 0; i < stringBuilder.length(); i += 8, index++) {
            String strByte;
            //说明最后一位不够8位
            if (i + 8 > stringBuilder.length()) {
                //从i位置直接取到最后
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte二进制数转成byte放入byte数组，放入huffmanCodesBytes
            huffmanCodesBytes[index] = (byte) Integer.parseInt(strByte, 2);
        }
        return huffmanCodesBytes;
    }

    /**
     * 为了调用方便，重载getCodes方法
     */
    private static Map<Byte, String> getCodes(Node root) {
        //判空
        Objects.requireNonNull(root);
        //处理root左子树
        getCodes(root.left, "0", stringBuilder);
        //处理root右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }
    /*
      生成赫夫曼树对应的赫夫曼编码
      思路：
      1、将赫夫曼编码表存放咋Map<Byte,String> 形式
         32->01 97->100 100->11000...等等[形式]不完全一样
      2、在生成赫夫曼编码表时，需要拼接路径，定义一个StringBuilder 存储某个叶子节点的路径
     */
    /**
     * 定义Map
     */
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    /**
     * 定义StringBuilder
     */
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 功能：将传入的node节点的所有叶子节点的赫夫曼编码得到，并存放到huffmanCodes集合中
     *
     * @param node          传入的节点
     * @param code          路径：左子节点是0，右子节点是1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code加入到stringBuilder2
        stringBuilder2.append(code);
        //如果node=null不处理
        if (node != null) {
            //判断当前node是叶子节点还是非叶子节点
            //非叶子节点
            if (node.data == null) {
                //递归处理
                //向左递归
                // 传入当前节点的左节点，code因为规定左路径为0，所以传入0，将该string-builder放入，递归处理继续添加
                getCodes(node.left, "0", stringBuilder2);
                //向右递归，同上,但是路径值改为1
                getCodes(node.right, "1", stringBuilder2);
            } else { //说明是叶子节点
                //代表已经找到了某个节点的最后
                //将该叶子节点存入到哈夫曼编码集合里，k->该叶子结点的数据，v->该叶子结点的值
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }

    //前序遍历的方法
    private static void preOrder(Node root) {
        if (root == null) {
            System.out.println("哈夫曼树为空");
            return;
        }
        root.preOrder();
    }

    /**
     * @param bytes 接收字节数
     * @return 返回Node集合</>
     */
    public static List<Node> getNodes(byte[] bytes) {
        //1、创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<>();
        //遍历bytes，统计每个byte出现的字数->map
        //k->数据，v->出现次数
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            //说明该数据还没创建->不存在
            //设置当前数据出现次数为1
            /*
              方法说明：
              1、进入该方法后先判断第三个函数参数和value值是否为空，
              2、内部调用get（key）方法获取旧值
              3、创建一个newValue新值-》 如果旧值不为空就使用提供的函数参数的方法，这里提供了Integer的sum方法
                 在内部将获取的旧值与提供的新值进行相加，如果为空就直接将该key的值设置为提供的value
              4、如果上述操作完毕newValue还是null值，说明给定的value和原key的旧值都为空，那么就将该key删除->remove(key)
              5、如果newValue不为空，就直接调用put（key,newValue）方法来存储
              6、方法结束后返回新值
             */
            counts.merge(b, 1, Integer::sum);
        }
        //把每个键值对转成一个Node对象，并加入到nodes集合
        //遍历Map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    /**
     * 创建赫夫曼数
     *
     * @param nodes 节点集合
     * @return 赫夫曼殊
     */
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序，从小到大
            Collections.sort(nodes);
            //取出第一颗最小的二叉树
            Node left = nodes.get(0);
            //去除第二课最小
            Node right = nodes.get(1);
            //创建两树的父节点
            Node parent = new Node(null, left.weight + right.weight);
            //设置父节点的子树为上面获取的两树
            parent.left = left;
            parent.right = right;
            //将处理过的两颗二叉树从nodes移除
            nodes.remove(left);
            nodes.remove(right);
            //将新的二叉树加入到nodes
            nodes.add(parent);
        }
        //返回最后一个节点
        return nodes.get(0);
    }
}

/**
 * 创建node,带数据和权值
 */
class Node implements Comparable<Node> {
    /**
     * 存放数据本身 'a'=>97
     */
    Byte data;
    /**
     * 权值表示字符出现的次数
     */
    int weight;
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{data=" + data + ",weight=" + weight + "}";
    }
}